<!DOCTYPE html>
<html>
<head><meta name="generator" content="Hexo 3.9.0">
  <!-- hexo-inject:begin --><!-- hexo-inject:end --><meta charset="utf-8">
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">



<title>
  
    Archive: 2019
  
</title>

<meta name="description" content="I am a current master at UPENN. This page serves as a record of my life. I may post study blogs, daily blogs, and personal opions. XD">
<meta property="og:type" content="website">
<meta property="og:title" content="Zexi &quot;Josh&quot; Jin">
<meta property="og:url" content="http://yoursite.com/archives/2019/index.html">
<meta property="og:site_name" content="Zexi &quot;Josh&quot; Jin">
<meta property="og:description" content="I am a current master at UPENN. This page serves as a record of my life. I may post study blogs, daily blogs, and personal opions. XD">
<meta property="og:locale" content="en">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="Zexi &quot;Josh&quot; Jin">
<meta name="twitter:description" content="I am a current master at UPENN. This page serves as a record of my life. I may post study blogs, daily blogs, and personal opions. XD">


  <link rel="alternative" href="/atom.xml" title="Zexi &#34;Josh&#34; Jin" type="application/atom+xml">



  <link rel="icon" href="/favicon.png">


<link rel="stylesheet" href="/perfect-scrollbar/css/perfect-scrollbar.min.css">
<link rel="stylesheet" href="/styles/main.css"><!-- hexo-inject:begin --><!-- hexo-inject:end -->






</head>
<body>
  <!-- hexo-inject:begin --><!-- hexo-inject:end --><div class="mobile-header">
  <button class="sidebar-toggle" type="button">
    <span class="icon-bar"></span>
    <span class="icon-bar"></span>
    <span class="icon-bar"></span>
  </button>
  <a class="title" href="/">Zexi &#34;Josh&#34; Jin</a>
</div>

  <div class="main-container">
    <div class="sidebar">
  <div class="header">
    <h1 class="title"><a href="/">Zexi &#34;Josh&#34; Jin</a></h1>
    
    <div class="info">
      <div class="content">
        
          <div class="description">I am a current master at UPENN. This page serves as a record of my life. I may post study blogs, daily blogs, and personal opions. XD</div>
        
        
      </div>
      
        <div class="avatar">
          
            <a href="/about"><img src="https://i.ibb.co/XXV2FLb/Screen-Shot-2019-10-17-at-12-31-49-PM.png"></a>
          
        </div>
      
    </div>
  </div>
  <div class="body">
    
      
        <ul class="nav">
          
            
              <li class="category-list-container">
                <a href="javascript:;">Category</a>
                <ul class="category-list"><li class="category-list-item"><a class="category-list-link" href="/categories/backend/">backend</a><span class="category-list-count">2</span></li><li class="category-list-item"><a class="category-list-link" href="/categories/data-analysis/">data analysis</a><span class="category-list-count">3</span></li><li class="category-list-item"><a class="category-list-link" href="/categories/data-structure/">data structure</a><span class="category-list-count">4</span></li><li class="category-list-item"><a class="category-list-link" href="/categories/photos/">photos</a><span class="category-list-count">2</span></li></ul>
              </li>
            
          
            
              <li class="tag-list-container">
                <a href="javascript:;">Tag</a>
                <ul class="tag-list"><li class="tag-list-item"><a class="tag-list-link" href="/tags/LeetCode/">LeetCode</a><span class="tag-list-count">3</span></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/algorithm/">algorithm</a><span class="tag-list-count">4</span></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/backend/">backend</a><span class="tag-list-count">1</span></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/backtrack/">backtrack</a><span class="tag-list-count">2</span></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/binary-tree/">binary tree</a><span class="tag-list-count">1</span></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/concurrency/">concurrency</a><span class="tag-list-count">1</span></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/django/">django</a><span class="tag-list-count">1</span></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/java/">java</a><span class="tag-list-count">4</span></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/new-york/">new york</a><span class="tag-list-count">1</span></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/pandas/">pandas</a><span class="tag-list-count">2</span></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/photos/">photos</a><span class="tag-list-count">2</span></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/python/">python</a><span class="tag-list-count">4</span></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/roc-auc/">roc-auc</a><span class="tag-list-count">1</span></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/sorting/">sorting</a><span class="tag-list-count">1</span></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/travel/">travel</a><span class="tag-list-count">2</span></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/traversal/">traversal</a><span class="tag-list-count">1</span></li></ul>
              </li>
            
          
            
              <li class="archive-list-container">
                <a href="javascript:;">Archive</a>
                <ul class="archive-list"><li class="archive-list-item"><a class="archive-list-link" href="/archives/2019/">2019</a><span class="archive-list-count">10</span></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2018/">2018</a><span class="archive-list-count">1</span></li></ul>
              </li>
            
          
        </ul>
      
        <ul class="nav">
          
            
              <li>
                <a href="/" title="Homepage">Homepage</a>
              </li>
            
          
            
              <li>
                <a href="/about" title="About">About</a>
              </li>
            
          
        </ul>
      
    
  </div>
</div>

    <div class="main-content">
      
        <div style="max-width: 1000px">
      
          

  
  
    
      
      
      <section class="archives-wrap">
        <div class="archive-year-wrap">
          <h1><a href="/archives/2019" class="archive-year">2019</a></h1>
        </div>
        <div class="post-list">
    
  

    <div class="post-list-item article">
      <h3 class="article-header">
        <a href="/2019/11/21/random-pandas-note-1/">
  Random Pandas Note 2
</a>

      </h3>
      

      <div class="article-info">
        <a href="/2019/11/21/random-pandas-note-1/"><span class="article-date">
  2019-11-21
</span>
</a>
        
	<span class="article-category tagcloud">
	<ul class="article-category-list"><li class="article-category-list-item"><a class="article-category-list-link" href="/categories/data-analysis/">data analysis</a></li></ul>
	</span>


        
	<span class="article-tag tagcloud">
		<ul class="article-tag-list"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/pandas/">pandas</a></li><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/python/">python</a></li></ul>
	</span>


      </div>
      <div class="article-entry">
        
          <p>Reference: <a href="https://www.mikulskibartosz.name/how-to-split-a-list-inside-a-dataframe-cell-into-rows-in-pandas/" target="_blank" rel="noopener">https://www.mikulskibartosz.name/how-to-split-a-list-inside-a-dataframe-cell-into-rows-in-pandas/</a></p>
<p>Given a table containing a column of lists, like:</p>
<div class="table-container">
<table>
<thead>
<tr>
<th style="text-align:center">id</th>
<th style="text-align:center">name</th>
<th style="text-align:center">tags</th>
</tr>
</thead>
<tbody>
<tr>
<td style="text-align:center">1</td>
<td style="text-align:center">winter squash</td>
<td style="text-align:center">[&#x2018;60-minutes&#x2019;, &#x2018;time-to-make&#x2019;, &#x2018;healthy&#x2019;]</td>
</tr>
<tr>
<td style="text-align:center">2</td>
<td style="text-align:center">braised pork</td>
<td style="text-align:center">[&#x2018;2-hours-more&#x2019;, &#x2018;time-to-make&#x2019;, &#x2018;chinese&#x2019;]</td>
</tr>
<tr>
<td style="text-align:center">3</td>
<td style="text-align:center">chilli Beef</td>
<td style="text-align:center">[&#x2018;4-hours-more&#x2019;, &#x2018;chinese&#x2019;]</td>
</tr>
</tbody>
</table>
</div>
<p>Like the &#x2018;unwind&#x2019; function in mongodb, to turn it into:</p>
<div class="table-container">
<table>
<thead>
<tr>
<th>id</th>
<th>name</th>
<th>tags</th>
</tr>
</thead>
<tbody>
<tr>
<td>1</td>
<td>winter squash</td>
<td>&#x2018;60-minutes&#x2019;</td>
</tr>
<tr>
<td>1</td>
<td>winter squash</td>
<td>&#x2018;time-to-make&#x2019;</td>
</tr>
<tr>
<td>1</td>
<td>winter squash</td>
<td>&#x2018;healthy&#x2019;</td>
</tr>
<tr>
<td>2</td>
<td>braised pork</td>
<td>&#x2018;2-hours-more&#x2019;</td>
</tr>
<tr>
<td>2</td>
<td>braised pork</td>
<td>&#x2018;time-to-make&#x2019;</td>
</tr>
<tr>
<td>2</td>
<td>braised pork</td>
<td>&#x2018;chinese&#x2019;</td>
</tr>
<tr>
<td>3</td>
<td>chilli Beef</td>
<td>&#x2018;4-hours-more&#x2019;</td>
</tr>
<tr>
<td>3</td>
<td>chilli Beef</td>
<td>&#x2018;chinese&#x2019;</td>
</tr>
</tbody>
</table>
</div>
<p>Here&#x2019;s who we do it:</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line">tags_df[&apos;tags&apos;] = tags_df.tags.apply(lambda x: x[1:-1].split(&apos;,&apos;))</span><br><span class="line">clean_tag_df = tags_df.tags.apply(pd.Series).merge(tags_df, right_index = True, left_index = True) \</span><br><span class="line">    .drop([&quot;tags&quot;], axis = 1) \</span><br><span class="line">    .melt(id_vars = [&apos;recipe_id&apos;], value_name = &quot;tags&quot;) \</span><br><span class="line">    .drop(&quot;variable&quot;, axis = 1).dropna()</span><br></pre></td></tr></table></figure>
<p>Breaking it down, we have the following to turn the tags from a string into a list of strings<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">tags_df[&apos;tags&apos;] = tags_df.tags.apply(lambda x: x[1:-1].split(&apos;,&apos;))</span><br></pre></td></tr></table></figure></p>
<p>Next step, turning a list of tags into multiple columns&#xFF1A;<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">tags_df.tags.apply(pd.Series)</span><br></pre></td></tr></table></figure></p>
<p>It turns the chart like:</p>
<div class="table-container">
<table>
<thead>
<tr>
<th>1</th>
<th>2</th>
<th>3</th>
</tr>
</thead>
<tbody>
<tr>
<td>&#x2018;60-minutes&#x2019;</td>
<td>&#x2018;time-to-make&#x2019;</td>
<td>&#x2018;healthy&#x2019; </td>
</tr>
<tr>
<td>&#x2018;2-hours-more&#x2019;</td>
<td>&#x2018;time-to-make&#x2019;</td>
<td>&#x2018;chinese&#x2019;</td>
</tr>
<tr>
<td>&#x2018;4-hours-more&#x2019;</td>
<td>&#x2018;chinese&#x2019;</td>
<td>NaN </td>
</tr>
</tbody>
</table>
</div>
<p>Then, we join tags with the rest of the list:<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">prev_df.merge(tags_df, right_index = True, left_index = True)</span><br></pre></td></tr></table></figure></p>
<p>Then, we drop the duplicated &#x201C;tags&#x201D; column and unwind different columns of the tags into different rows:<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">prev_df.drop([&quot;tags&quot;], axis = 1).melt(id_vars = [&apos;recipe_id&apos;], value_name = &quot;tags&quot;)</span><br></pre></td></tr></table></figure></p>
<p>Lastly, we remove the &#x201C;variable&#x201D; column, which we might not need:<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">prev_df.drop(&quot;variable&quot;, axis = 1).dropna()</span><br></pre></td></tr></table></figure></p>

        
      </div>
    </div>

  

  
  
    
  

    <div class="post-list-item article">
      <h3 class="article-header">
        <a href="/2019/10/23/tree-traversal-1/">
  Binary Tree Traversal, Part 1
</a>

      </h3>
      

      <div class="article-info">
        <a href="/2019/10/23/tree-traversal-1/"><span class="article-date">
  2019-10-23
</span>
</a>
        
	<span class="article-category tagcloud">
	<ul class="article-category-list"><li class="article-category-list-item"><a class="article-category-list-link" href="/categories/data-structure/">data structure</a></li></ul>
	</span>


        
	<span class="article-tag tagcloud">
		<ul class="article-tag-list"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/LeetCode/">LeetCode</a></li><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/algorithm/">algorithm</a></li><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/binary-tree/">binary tree</a></li><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/java/">java</a></li><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/traversal/">traversal</a></li></ul>
	</span>


      </div>
      <div class="article-entry">
        
          <p><strong>outline:</strong></p>
<ol>
<li>pre-order, post-order, in-order traversal of binary tree</li>
<li>level-order traversal of binary tree</li>
</ol>
<h2 id="pre-order-post-order-in-order-traversal-of-binary-tree"><a href="#pre-order-post-order-in-order-traversal-of-binary-tree" class="headerlink" title="pre-order, post-order, in-order traversal of binary tree"></a>pre-order, post-order, in-order traversal of binary tree</h2><p><strong>pre-order:</strong><br><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> </span>{</span><br><span class="line">    <span class="function"><span class="keyword">public</span> List&lt;Integer&gt; <span class="title">preorderTraversal</span><span class="params">(TreeNode root)</span> </span>{</span><br><span class="line">        List&lt;Integer&gt; res = <span class="keyword">new</span> ArrayList&lt;Integer&gt;();</span><br><span class="line">        preorder(root, res);</span><br><span class="line">        <span class="keyword">return</span> res;</span><br><span class="line">    }</span><br><span class="line">    </span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">preorder</span><span class="params">(TreeNode node, List res)</span> </span>{</span><br><span class="line">        <span class="keyword">if</span> (node != <span class="keyword">null</span>) {</span><br><span class="line">            res.add(node.val);</span><br><span class="line">            preorder(node.left, res);</span><br><span class="line">            preorder(node.right, res);</span><br><span class="line">        }</span><br><span class="line">    }</span><br><span class="line">}</span><br></pre></td></tr></table></figure></p>
<p><strong>post-order:</strong><br><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> </span>{</span><br><span class="line">    <span class="function"><span class="keyword">public</span> List&lt;Integer&gt; <span class="title">postorderTraversal</span><span class="params">(TreeNode root)</span> </span>{</span><br><span class="line">        List&lt;Integer&gt; res = <span class="keyword">new</span> ArrayList&lt;Integer&gt;();</span><br><span class="line">        postorder(root, res);</span><br><span class="line">        <span class="keyword">return</span> res;</span><br><span class="line">    }</span><br><span class="line">    </span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">postorder</span><span class="params">(TreeNode node, List res)</span> </span>{</span><br><span class="line">        <span class="keyword">if</span> (node != <span class="keyword">null</span>) {</span><br><span class="line">            postorder(node.left, res);</span><br><span class="line">            postorder(node.right, res);</span><br><span class="line">            res.add(node.val);</span><br><span class="line">        }</span><br><span class="line">    }</span><br><span class="line">}</span><br></pre></td></tr></table></figure></p>
<p><strong>in-order:</strong><br><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> </span>{</span><br><span class="line">    <span class="function"><span class="keyword">public</span> List&lt;Integer&gt; <span class="title">inorderTraversal</span><span class="params">(TreeNode root)</span> </span>{</span><br><span class="line">        List&lt;Integer&gt; res = <span class="keyword">new</span> ArrayList&lt;Integer&gt;();</span><br><span class="line">        inorder(root, res);</span><br><span class="line">        <span class="keyword">return</span> res;</span><br><span class="line">    }</span><br><span class="line">    </span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">inorder</span><span class="params">(TreeNode node, List res)</span> </span>{</span><br><span class="line">        <span class="keyword">if</span> (node != <span class="keyword">null</span>) {</span><br><span class="line">            inorder(node.left, res);</span><br><span class="line">            res.add(node.val);</span><br><span class="line">            inorder(node.right, res);</span><br><span class="line">        }</span><br><span class="line">    }</span><br><span class="line">}</span><br></pre></td></tr></table></figure></p>
<h2 id="level-order"><a href="#level-order" class="headerlink" title="level-order:"></a>level-order:</h2><p><strong>recursive method:</strong><br><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> </span>{</span><br><span class="line">    <span class="keyword">public</span> List&lt;List&lt;Integer&gt;&gt; levelOrder(TreeNode root) {</span><br><span class="line">        List&lt;List&lt;Integer&gt;&gt; res = <span class="keyword">new</span> ArrayList&lt;List&lt;Integer&gt;&gt;();</span><br><span class="line">        <span class="keyword">int</span> level = <span class="number">0</span>;</span><br><span class="line">        <span class="keyword">if</span> (root == <span class="keyword">null</span>)</span><br><span class="line">            <span class="keyword">return</span> res;</span><br><span class="line">        level_recur(root, res, level);</span><br><span class="line">        <span class="keyword">return</span> res;</span><br><span class="line">    }</span><br><span class="line">    </span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">level_recur</span><span class="params">(TreeNode node, List&lt;List&lt;Integer&gt;&gt; res, <span class="keyword">int</span> level)</span> </span>{</span><br><span class="line">        <span class="comment">// add new level if necessary</span></span><br><span class="line">        <span class="keyword">if</span> (res.size() == level)</span><br><span class="line">            res.add(<span class="keyword">new</span> ArrayList&lt;Integer&gt;());      </span><br><span class="line">        <span class="comment">// add current value to corresponding level</span></span><br><span class="line">        res.get(level).add(node.val);</span><br><span class="line">        <span class="comment">// recursion</span></span><br><span class="line">        <span class="keyword">if</span> (node.left != <span class="keyword">null</span>)</span><br><span class="line">            level_recur(node.left, res, level+<span class="number">1</span>);</span><br><span class="line">        <span class="keyword">if</span> (node.right != <span class="keyword">null</span>)</span><br><span class="line">            level_recur(node.right, res, level+<span class="number">1</span>);</span><br><span class="line">    }</span><br><span class="line">}</span><br></pre></td></tr></table></figure></p>
<p><strong>iterative method:</strong><br><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> </span>{</span><br><span class="line">    <span class="keyword">public</span> List&lt;List&lt;Integer&gt;&gt; levelOrder(TreeNode root) {</span><br><span class="line">        List&lt;List&lt;Integer&gt;&gt; res = <span class="keyword">new</span> ArrayList&lt;List&lt;Integer&gt;&gt;();</span><br><span class="line">        <span class="keyword">if</span> (root == <span class="keyword">null</span>)</span><br><span class="line">            <span class="keyword">return</span> res;</span><br><span class="line">        <span class="keyword">int</span> level = <span class="number">0</span>;</span><br><span class="line">        Queue&lt;TreeNode&gt; queue = <span class="keyword">new</span> LinkedList&lt;TreeNode&gt;();</span><br><span class="line">        queue.add(root);</span><br><span class="line">        <span class="keyword">while</span>(!queue.isEmpty()) {</span><br><span class="line">            res.add(<span class="keyword">new</span> ArrayList&lt;Integer&gt;());</span><br><span class="line">            <span class="keyword">int</span> level_len = queue.size();</span><br><span class="line">            <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; level_len; i++) {</span><br><span class="line">                TreeNode cur = queue.remove();</span><br><span class="line">                res.get(level).add(cur.val);</span><br><span class="line">                <span class="keyword">if</span> (cur.left != <span class="keyword">null</span>)</span><br><span class="line">                    queue.add(cur.left);</span><br><span class="line">                <span class="keyword">if</span> (cur.right != <span class="keyword">null</span>)</span><br><span class="line">                    queue.add(cur.right);</span><br><span class="line">            }</span><br><span class="line">            level += <span class="number">1</span>;</span><br><span class="line">        }</span><br><span class="line">        <span class="keyword">return</span> res;</span><br><span class="line">    }</span><br><span class="line">}</span><br></pre></td></tr></table></figure></p>

        
      </div>
    </div>

  

  
  
    
  

    <div class="post-list-item article">
      <h3 class="article-header">
        <a href="/2019/10/22/backtracking-summaries-1/">
  Backtracking Leetcode Summary, Part 2
</a>

      </h3>
      

      <div class="article-info">
        <a href="/2019/10/22/backtracking-summaries-1/"><span class="article-date">
  2019-10-22
</span>
</a>
        
	<span class="article-category tagcloud">
	<ul class="article-category-list"><li class="article-category-list-item"><a class="article-category-list-link" href="/categories/data-structure/">data structure</a></li></ul>
	</span>


        
	<span class="article-tag tagcloud">
		<ul class="article-tag-list"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/LeetCode/">LeetCode</a></li><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/algorithm/">algorithm</a></li><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/backtrack/">backtrack</a></li><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/java/">java</a></li></ul>
	</span>


      </div>
      <div class="article-entry">
        
          <ol>
<li>Subsets</li>
<li>Palindrome</li>
<li>Combination Sum, repeated number used</li>
<li>Combination Sum, unique number used</li>
</ol>
<h3 id="Subsets"><a href="#Subsets" class="headerlink" title="Subsets:"></a>Subsets:</h3><p><strong>Problem Description:</strong> Given a set of distinct integers, nums, return all possible subsets (the power set). Note: The solution set must not contain duplicate subsets.  </p>
<p><strong>Few Key Points:</strong>  </p>
<ul>
<li>This algorithm is very close to that of permutation. The only difference is that this counts for subsets instead of permutations.</li>
<li>One of the key point is to keep the order, don&#x2019;t permute like the permutation algorithm</li>
</ul>
<p><strong>Code:</strong><br>backtracking part, takes parameters:  </p>
<ol>
<li>result: LinkedList<arraylist<integer>&gt;</arraylist<integer></li>
<li>current: ArrayList<integer></integer></li>
<li>nums: nums to extract from</li>
<li>cur_idx: current index  </li>
</ol>
<p>Note: when adding to result, convert the current list into a new list<br><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">backtrack</span><span class="params">(List&lt;List&lt;Integer&gt;&gt; l, </span></span></span><br><span class="line"><span class="function"><span class="params">                      List&lt;Integer&gt; tmpList, </span></span></span><br><span class="line"><span class="function"><span class="params">                      <span class="keyword">int</span> [] nums, </span></span></span><br><span class="line"><span class="function"><span class="params">                      <span class="keyword">int</span> start)</span> </span>{</span><br><span class="line">    l.add(<span class="keyword">new</span> ArrayList&lt;&gt;(tmpList));</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = start; i &lt; nums.length; i++) {</span><br><span class="line">        tmpList.add(nums[i]);</span><br><span class="line">        backtrack(l, tmpList, nums, i+<span class="number">1</span>);</span><br><span class="line">        tmpList.remove(tmpList.size() - <span class="number">1</span>);</span><br><span class="line">    }</span><br><span class="line">}</span><br></pre></td></tr></table></figure></p>
<p>The solution part:<br><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> List&lt;List&lt;Integer&gt;&gt; subsets(<span class="keyword">int</span>[] nums) {</span><br><span class="line">    List&lt;List&lt;Integer&gt;&gt; res = <span class="keyword">new</span> LinkedList&lt;&gt;();</span><br><span class="line">    List&lt;Integer&gt; tmp = <span class="keyword">new</span> ArrayList&lt;Integer&gt;();</span><br><span class="line">    <span class="keyword">int</span> start = <span class="number">0</span>;</span><br><span class="line">    backtrack(res, tmp, nums, start);</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">}</span><br></pre></td></tr></table></figure></p>
<h3 id="Palindrome"><a href="#Palindrome" class="headerlink" title="Palindrome:"></a>Palindrome:</h3><p><strong>Problem Description:</strong> Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s.<br>e.g.:<br>Input: &#x201C;aab&#x201D;<br>Output:<br>[[&#x201C;aa&#x201D;,&#x201D;b&#x201D;],<br>  [&#x201C;a&#x201D;,&#x201D;a&#x201D;,&#x201D;b&#x201D;]]</p>
<p><strong>Few Key Points:</strong>  </p>
<ul>
<li>An utility function can be used to determine if str is palindrome or not.</li>
</ul>
<p><strong>Code:</strong><br>backtrack:<br><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">backtrack</span><span class="params">(List&lt;List&lt;String&gt;&gt; result, </span></span></span><br><span class="line"><span class="function"><span class="params">                      List&lt;String&gt; tmp, </span></span></span><br><span class="line"><span class="function"><span class="params">                      String str, </span></span></span><br><span class="line"><span class="function"><span class="params">                      <span class="keyword">int</span> index)</span> </span>{</span><br><span class="line">    <span class="keyword">if</span> (index == str.length()) </span><br><span class="line">        result.add(<span class="keyword">new</span> ArrayList&lt;String&gt;(tmp));</span><br><span class="line">    <span class="keyword">else</span> {</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = index; i &lt; str.length(); i++) {</span><br><span class="line">            <span class="keyword">if</span> (isPalindrome(str, index, i)) {</span><br><span class="line">                tmp.add(str.substring(index, i+<span class="number">1</span>));</span><br><span class="line">                backtrack(result, tmp, str, i+<span class="number">1</span>);</span><br><span class="line">                tmp.remove(tmp.size()-<span class="number">1</span>);</span><br><span class="line">            }</span><br><span class="line">        }</span><br><span class="line">    }</span><br><span class="line">}</span><br></pre></td></tr></table></figure></p>
<p>Check if str is palindrome:<br><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">isPalindrome</span><span class="params">(String str, <span class="keyword">int</span> s, <span class="keyword">int</span> e)</span> </span>{</span><br><span class="line">    <span class="keyword">while</span> (s &lt; e) {</span><br><span class="line">        <span class="keyword">if</span> (str.charAt(s++) != str.charAt(e--))</span><br><span class="line">            <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">    }</span><br><span class="line">    <span class="keyword">return</span> <span class="keyword">true</span>;</span><br><span class="line">}</span><br></pre></td></tr></table></figure></p>
<p>The solution part:<br><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> List&lt;List&lt;String&gt;&gt; partition(String s) {</span><br><span class="line">    List&lt;List&lt;String&gt;&gt; res = <span class="keyword">new</span> LinkedList&lt;List&lt;String&gt;&gt;();</span><br><span class="line">    List&lt;String&gt; list = <span class="keyword">new</span> ArrayList&lt;String&gt;();</span><br><span class="line">    <span class="keyword">int</span> idx = <span class="number">0</span>;</span><br><span class="line">    backtrack(res, list, s, idx);</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">}</span><br></pre></td></tr></table></figure></p>
<h3 id="Combination-Sum-repeat-allowed"><a href="#Combination-Sum-repeat-allowed" class="headerlink" title="Combination Sum, repeat allowed"></a>Combination Sum, repeat allowed</h3><p><strong>Problem Description:</strong> Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target. The same repeated number may be chosen from candidates unlimited number of times.<br>e.g.:<br>Input: candidates = [2,3,6,7], target = 7,<br>A solution set is:<br>[[7],<br>  [2,2,3]]  </p>
<p><strong>Codes:</strong><br>backtrack:<br><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">backtrack</span><span class="params">(List&lt;List&lt;Integer&gt;&gt; res, </span></span></span><br><span class="line"><span class="function"><span class="params">                 List&lt;Integer&gt; tmp, </span></span></span><br><span class="line"><span class="function"><span class="params">                 <span class="keyword">int</span>[] cand, </span></span></span><br><span class="line"><span class="function"><span class="params">                 <span class="keyword">int</span> rem, </span></span></span><br><span class="line"><span class="function"><span class="params">                 <span class="keyword">int</span> cur)</span> </span>{</span><br><span class="line">    <span class="keyword">if</span> (rem == <span class="number">0</span>) {</span><br><span class="line">        res.add(<span class="keyword">new</span> ArrayList&lt;Integer&gt;(tmp));</span><br><span class="line">    } <span class="keyword">else</span> <span class="keyword">if</span> (rem &lt; <span class="number">0</span>) {</span><br><span class="line">        <span class="keyword">return</span>;</span><br><span class="line">    } <span class="keyword">else</span> {</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = cur; i &lt; cand.length; i++) {</span><br><span class="line">            <span class="keyword">if</span> (rem &gt;= cand[i]) {</span><br><span class="line">                tmp.add(cand[i]);</span><br><span class="line">                backtrack(res, tmp, cand, rem - cand[i], i);</span><br><span class="line">                tmp.remove(tmp.size()-<span class="number">1</span>);</span><br><span class="line">            } <span class="keyword">else</span> {</span><br><span class="line">                <span class="keyword">break</span>;</span><br><span class="line">            }</span><br><span class="line">        }</span><br><span class="line">    }</span><br><span class="line">}</span><br></pre></td></tr></table></figure></p>
<p>The solution part:<br><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> List&lt;List&lt;Integer&gt;&gt; combinationSum(<span class="keyword">int</span>[] candidates, <span class="keyword">int</span> target) {</span><br><span class="line">    List&lt;List&lt;Integer&gt;&gt; res = <span class="keyword">new</span> LinkedList&lt;&gt;();</span><br><span class="line">    List&lt;Integer&gt; tmp = <span class="keyword">new</span> ArrayList&lt;Integer&gt;();</span><br><span class="line">    <span class="keyword">int</span> cur = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">int</span> rem = target;</span><br><span class="line">    Arrays.sort(candidates);</span><br><span class="line">    backtrack(res, tmp, candidates, rem, cur);</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">}</span><br></pre></td></tr></table></figure></p>
<h3 id="Combination-Sum-no-repeats"><a href="#Combination-Sum-no-repeats" class="headerlink" title="Combination Sum, no repeats"></a>Combination Sum, no repeats</h3><p><strong>Problem Description:</strong> Same as combination sum, with only difference that each number can only be used once.  </p>
<p><strong>Codes:</strong><br>backtrack: (added while loop to eliminate repeating results)<br><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">backtrack</span><span class="params">(List&lt;List&lt;Integer&gt;&gt; res, </span></span></span><br><span class="line"><span class="function"><span class="params">                 List&lt;Integer&gt; tmp, </span></span></span><br><span class="line"><span class="function"><span class="params">                 <span class="keyword">int</span>[] cand, </span></span></span><br><span class="line"><span class="function"><span class="params">                 <span class="keyword">int</span> rem, </span></span></span><br><span class="line"><span class="function"><span class="params">                 <span class="keyword">int</span> cur)</span> </span>{</span><br><span class="line">    <span class="keyword">if</span> (rem == <span class="number">0</span>) {</span><br><span class="line">        res.add(<span class="keyword">new</span> ArrayList&lt;Integer&gt;(tmp));</span><br><span class="line">    } <span class="keyword">else</span> <span class="keyword">if</span> (rem &lt; <span class="number">0</span>) {</span><br><span class="line">        <span class="keyword">return</span>;</span><br><span class="line">    } <span class="keyword">else</span> {</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = cur; i &lt; cand.length; i++) {</span><br><span class="line">            <span class="keyword">if</span> (rem &gt;= cand[i]) {</span><br><span class="line">                tmp.add(cand[i]);                    </span><br><span class="line">                backtrack(res, tmp, cand, rem - cand[i], i+<span class="number">1</span>);</span><br><span class="line">                tmp.remove(tmp.size()-<span class="number">1</span>);</span><br><span class="line">                <span class="keyword">while</span> (i &lt; cand.length-<span class="number">1</span> &amp;&amp; cand[i] == cand[i+<span class="number">1</span>])</span><br><span class="line">                    i += <span class="number">1</span>;</span><br><span class="line">            } <span class="keyword">else</span> {</span><br><span class="line">                <span class="keyword">break</span>;</span><br><span class="line">            }</span><br><span class="line">        }</span><br><span class="line">    }</span><br><span class="line">}</span><br></pre></td></tr></table></figure></p>
<p>The solution part is the same as before. </p>

        
      </div>
    </div>

  

  
  
    
  

    <div class="post-list-item article">
      <h3 class="article-header">
        <a href="/2019/10/21/ROC-AUC-curve/">
  Confusion Matrix Summary
</a>

      </h3>
      
  <div class="article-gallery article-gallery-photos" itemscope itemtype="http://schema.org/ImageGallery">
    
      <figure class="article-gallery-img" itemprop="associatedMedia" itemscope itemtype="http://schema.org/ImageObject">
        <a href="https://i.ibb.co/F483Wfr/20160120112441421.png" itemprop="contentUrl" rel="gallery_ck3ah5hir002qaypqjsnis0w5" title style="background-image: url(https://i.ibb.co/F483Wfr/20160120112441421.png)">
          <img src="https://i.ibb.co/F483Wfr/20160120112441421.png" itemprop="thumbnail" alt>
        </a>
        <figcaption itemprop="caption description"></figcaption>
      </figure>
    
  </div>


      <div class="article-info">
        <a href="/2019/10/21/ROC-AUC-curve/"><span class="article-date">
  2019-10-21
</span>
</a>
        
	<span class="article-category tagcloud">
	<ul class="article-category-list"><li class="article-category-list-item"><a class="article-category-list-link" href="/categories/data-analysis/">data analysis</a></li></ul>
	</span>


        
	<span class="article-tag tagcloud">
		<ul class="article-tag-list"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/roc-auc/">roc-auc</a></li></ul>
	</span>


      </div>
      <div class="article-entry">
        
          <p>A simple cheat-sheet for confusion matrix.</p>

        
      </div>
    </div>

  

  
  
    
  

    <div class="post-list-item article">
      <h3 class="article-header">
        <a href="/2019/10/19/random-pandas-note/">
  Random Pandas Note 1
</a>

      </h3>
      

      <div class="article-info">
        <a href="/2019/10/19/random-pandas-note/"><span class="article-date">
  2019-10-19
</span>
</a>
        
	<span class="article-category tagcloud">
	<ul class="article-category-list"><li class="article-category-list-item"><a class="article-category-list-link" href="/categories/data-analysis/">data analysis</a></li></ul>
	</span>


        
	<span class="article-tag tagcloud">
		<ul class="article-tag-list"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/pandas/">pandas</a></li><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/python/">python</a></li></ul>
	</span>


      </div>
      <div class="article-entry">
        
          <p>To change a row value based on more than one conditions, use the following:<br><figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">df[<span class="string">&apos;A&apos;</span>] = np.where(((df[<span class="string">&apos;B&apos;</span>] == <span class="string">&apos;some_value&apos;</span>) &amp; (df[<span class="string">&apos;C&apos;</span>] == <span class="string">&apos;some_other_value&apos;</span>)), true_value, false_value)</span><br></pre></td></tr></table></figure></p>
<p>Another equally efficient approach is using loc:<br>Note that this method does not give a default value when the condition is not met. So, the same code might be required to run twice or using .fillna() method.<br><figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">df.loc[(df.B == <span class="string">&apos;some_value&apos;</span>) | (df.C == <span class="string">&apos;some_other_value&apos;</span>), <span class="string">&apos;A&apos;</span>] = true_value</span><br></pre></td></tr></table></figure></p>
<p>ps: for &#x2018;and&#x2019; or &#x2018;or&#x2019; operation, use symbol &#x2018;&amp;&#x2019; or &#x2018;|&#x2019;.</p>

        
      </div>
    </div>

  

  
  
    
  

    <div class="post-list-item article">
      <h3 class="article-header">
        <a href="/2019/10/18/backtracking-summaries/">
  Backtracking Leetcode Summary, Part 1
</a>

      </h3>
      

      <div class="article-info">
        <a href="/2019/10/18/backtracking-summaries/"><span class="article-date">
  2019-10-18
</span>
</a>
        
	<span class="article-category tagcloud">
	<ul class="article-category-list"><li class="article-category-list-item"><a class="article-category-list-link" href="/categories/data-structure/">data structure</a></li></ul>
	</span>


        
	<span class="article-tag tagcloud">
		<ul class="article-tag-list"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/LeetCode/">LeetCode</a></li><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/algorithm/">algorithm</a></li><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/backtrack/">backtrack</a></li><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/java/">java</a></li></ul>
	</span>


      </div>
      <div class="article-entry">
        
          <ol>
<li>N-Queens</li>
<li>Permutation</li>
</ol>
<h3 id="N-Queens"><a href="#N-Queens" class="headerlink" title="N-Queens:"></a>N-Queens:</h3><p><strong>Problem Description:</strong> The n-queens puzzle is the problem of placing n queens on an n&#xD7;n chessboard such that no two queens attack each other. Given an integer n, return all distinct solutions to the n-queens puzzle. Each solution contains a distinct board configuration of the n-queens&#x2019; placement, where &#x2018;Q&#x2019; and &#x2018;.&#x2019; both indicate a queen and an empty space respectively.  </p>
<p><strong>Thought Process in Short:</strong> Backtracking with DFS. We know each row has one queen, so we move from top line to the bottom line line by line, checking each column, and two diagonals.  </p>
<p><strong>Few Key Points:</strong>  </p>
<ul>
<li>For all &#x201C;hill&#x201D; diagonals row + column = const, and for all &#x201C;dale&#x201D; diagonals row - column = const.</li>
<li>There could be the only one queen in a row and the only one queen in a column.</li>
</ul>
<p><strong>Algorithms:</strong>  </p>
<ol>
<li>Start from the first row = 0.</li>
<li>Iterate over the columns and try to put a queen in each column.<ol>
<li>If square (row, column) is not under attack<ol>
<li>Place the queen in (row, column) square.</li>
<li>Exclude one row, one column and two diagonals from further consideration.</li>
<li>If all rows are filled up row == N<ul>
<li>That means that we find out one more solution.  </li>
</ul>
</li>
<li>Else<ul>
<li>Proceed to place further queens backtrack(row + 1).</li>
</ul>
</li>
<li>Now backtrack : remove the queen from (row, column) square.</li>
</ol>
</li>
</ol>
</li>
</ol>
<p><strong>Codes</strong>:<br>Initialize log variables:<br><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">int</span> rows[];</span><br><span class="line"><span class="keyword">int</span> hills[];</span><br><span class="line"><span class="keyword">int</span> dales[];</span><br><span class="line"><span class="keyword">int</span> n;</span><br><span class="line">List&lt;List&lt;String&gt;&gt; output = <span class="keyword">new</span> ArrayList();</span><br><span class="line"><span class="keyword">int</span> queens[];</span><br></pre></td></tr></table></figure></p>
<p>Checking if a cell is under attack:<br><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">boolean</span> <span class="title">isNotUnderAttack</span><span class="params">(<span class="keyword">int</span> row, <span class="keyword">int</span> col)</span> </span>{</span><br><span class="line">    <span class="keyword">int</span> res = rows[col] + hills[row - col + <span class="number">2</span> * n] + dales[row + col];</span><br><span class="line">    <span class="keyword">if</span> (res == <span class="number">0</span>) {</span><br><span class="line">        <span class="keyword">return</span> <span class="keyword">true</span>;</span><br><span class="line">    } <span class="keyword">else</span> {</span><br><span class="line">        <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">    }</span><br><span class="line">}</span><br></pre></td></tr></table></figure></p>
<p>Method placing and removing queens:<br><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">placeQueen</span><span class="params">(<span class="keyword">int</span> row, <span class="keyword">int</span> col)</span> </span>{</span><br><span class="line">    queens[row] = col;</span><br><span class="line">    rows[col] = <span class="number">1</span>;</span><br><span class="line">    hills[row - col + <span class="number">2</span> * n] = <span class="number">1</span>;</span><br><span class="line">    dales[row + col] = <span class="number">1</span>;</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">removeQueen</span><span class="params">(<span class="keyword">int</span> row, <span class="keyword">int</span> col)</span> </span>{</span><br><span class="line">    queens[row] = <span class="number">0</span>;</span><br><span class="line">    rows[col] = <span class="number">0</span>;</span><br><span class="line">    hills[row - col + <span class="number">2</span> * n] = <span class="number">0</span>;</span><br><span class="line">    dales[row + col] = <span class="number">0</span>;</span><br><span class="line">}</span><br></pre></td></tr></table></figure></p>
<p>Adding a solution to existing solutions:<br><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">addSolution</span><span class="params">()</span> </span>{</span><br><span class="line">    List&lt;String&gt; solution = <span class="keyword">new</span> ArrayList&lt;String&gt;();</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; n; ++i) {</span><br><span class="line">        <span class="keyword">int</span> col = queens[i];</span><br><span class="line">        StringBuilder sb = <span class="keyword">new</span> StringBuilder();</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">0</span>; j &lt; col; ++j) {</span><br><span class="line">            sb.append(<span class="string">&quot;.&quot;</span>);</span><br><span class="line">        }</span><br><span class="line">        sb.append(<span class="string">&quot;Q&quot;</span>);</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">0</span>; j &lt; n - col - <span class="number">1</span>; ++j) {</span><br><span class="line">            sb.append(<span class="string">&quot;.&quot;</span>);</span><br><span class="line">        }</span><br><span class="line">        solution.add(sb.toString());</span><br><span class="line">    }</span><br><span class="line">    output.add(solution);</span><br><span class="line">}</span><br></pre></td></tr></table></figure></p>
<p>The actual backtracking process:<br><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">backtrack</span> <span class="params">(<span class="keyword">int</span> row)</span> </span>{</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> col = <span class="number">0</span>; col &lt; n; col++) {</span><br><span class="line">        <span class="keyword">if</span> (isNotUnderAttack(row, col)) {</span><br><span class="line">            placeQueen(row, col);</span><br><span class="line">            <span class="keyword">if</span> (row + <span class="number">1</span> == n) {</span><br><span class="line">                addSolution();</span><br><span class="line">            } <span class="keyword">else</span> {</span><br><span class="line">                backtrack(row + <span class="number">1</span>);</span><br><span class="line">            }</span><br><span class="line">            removeQueen(row, col);</span><br><span class="line">        }</span><br><span class="line">    }</span><br><span class="line">}</span><br></pre></td></tr></table></figure></p>
<p>Main function of solution:<br><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> List&lt;List&lt;String&gt;&gt; solveNQueens(<span class="keyword">int</span> n) {</span><br><span class="line">    <span class="keyword">this</span>.n = n;</span><br><span class="line">    rows = <span class="keyword">new</span> <span class="keyword">int</span>[n];</span><br><span class="line">    hills = <span class="keyword">new</span> <span class="keyword">int</span>[<span class="number">4</span> * n - <span class="number">1</span>];</span><br><span class="line">    dales = <span class="keyword">new</span> <span class="keyword">int</span>[<span class="number">2</span> * n - <span class="number">1</span>];</span><br><span class="line">    queens = <span class="keyword">new</span> <span class="keyword">int</span>[n];</span><br><span class="line">    </span><br><span class="line">    backtrack(<span class="number">0</span>);</span><br><span class="line">    <span class="keyword">return</span> output;</span><br><span class="line">}</span><br></pre></td></tr></table></figure></p>
<h3 id="Permutation"><a href="#Permutation" class="headerlink" title="Permutation:"></a>Permutation:</h3><p>One of the more basic backtracking problem.  </p>
<p><strong>Algorithms:</strong>  </p>
<ol>
<li>If the first integer to consider has index n that means that the current permutation is done.</li>
<li>Iterate over the integers from index first to index n - 1.<ol>
<li>Place i-th integer first in the permutation, i.e. swap(nums[first], nums[i]).</li>
<li>Proceed to create all permutations which starts from i-th integer : backtrack(first + 1).</li>
<li>Now backtrack, i.e. swap(nums[first], nums[i]) back.</li>
</ol>
</li>
</ol>
<p><strong>Code</strong><br>BFS to find solutions, then backtracking to reverse to previous states. The following is the backtracking part.<br><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">backtrack</span><span class="params">(<span class="keyword">int</span> n, </span></span></span><br><span class="line"><span class="function"><span class="params">                      ArrayList&lt;Integer&gt; nums, </span></span></span><br><span class="line"><span class="function"><span class="params">                      List&lt;List&lt;Integer&gt;&gt; res, </span></span></span><br><span class="line"><span class="function"><span class="params">                      <span class="keyword">int</span> first_idx)</span> </span>{</span><br><span class="line">    <span class="keyword">if</span> (first_idx == n) {</span><br><span class="line">        res.add(<span class="keyword">new</span> ArrayList&lt;Integer&gt;(nums));</span><br><span class="line">    }</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = first_idx; i &lt; n; i++) {</span><br><span class="line">        # swap first and ith</span><br><span class="line">        Collections.swap(nums, first_idx, i);</span><br><span class="line">        backtrack(n, nums, res, first_idx+<span class="number">1</span>);</span><br><span class="line">        # swap back to original</span><br><span class="line">        Collections.swap(nums, first_idx, i);</span><br><span class="line">    }</span><br><span class="line">}</span><br></pre></td></tr></table></figure></p>
<p>Main function of solution:<br><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> List&lt;List&lt;Integer&gt;&gt; permute(<span class="keyword">int</span>[] nums) {</span><br><span class="line">    List&lt;List&lt;Integer&gt;&gt; res = <span class="keyword">new</span> LinkedList();</span><br><span class="line">    ArrayList&lt;Integer&gt; nums_list = <span class="keyword">new</span> ArrayList&lt;Integer&gt;();</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> num : nums) {</span><br><span class="line">        nums_list.add(num);</span><br><span class="line">    }</span><br><span class="line">    <span class="keyword">int</span> n = nums.length;</span><br><span class="line">    backtrack(n, nums_list, res, <span class="number">0</span>);</span><br><span class="line">    <span class="keyword">return</span> res;</span><br><span class="line">}</span><br></pre></td></tr></table></figure></p>

        
      </div>
    </div>

  

  
  
    
  

    <div class="post-list-item article">
      <h3 class="article-header">
        <a href="/2019/10/17/new-york-20191011/">
  Oct 12th trip to New Yorks
</a>

      </h3>
      
  <div class="article-gallery article-gallery-photos" itemscope itemtype="http://schema.org/ImageGallery">
    
      <figure class="article-gallery-img" itemprop="associatedMedia" itemscope itemtype="http://schema.org/ImageObject">
        <a href="https://i.ibb.co/NLpzhbQ/IMG-4642.jpg" itemprop="contentUrl" rel="gallery_ck3ah5hhi0007aypq3gim194g" title="A snap-shot of NYC" style="background-image: url(https://i.ibb.co/NLpzhbQ/IMG-4642.jpg)">
          <img src="https://i.ibb.co/NLpzhbQ/IMG-4642.jpg" itemprop="thumbnail" alt="A snap-shot of NYC">
        </a>
        <figcaption itemprop="caption description">A snap-shot of NYC</figcaption>
      </figure>
    
  </div>


      <div class="article-info">
        <a href="/2019/10/17/new-york-20191011/"><span class="article-date">
  2019-10-17
</span>
</a>
        
	<span class="article-category tagcloud">
	<ul class="article-category-list"><li class="article-category-list-item"><a class="article-category-list-link" href="/categories/photos/">photos</a></li></ul>
	</span>


        
	<span class="article-tag tagcloud">
		<ul class="article-tag-list"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/new-york/">new york</a></li><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/photos/">photos</a></li><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/travel/">travel</a></li></ul>
	</span>


      </div>
      <div class="article-entry">
        
          <p>I took that picture with my iPhone. Kind of surprised by the light effect of that sunset.</p>

        
      </div>
    </div>

  

  
  
    
  

    <div class="post-list-item article">
      <h3 class="article-header">
        <a href="/2019/10/13/sort-summary-1/">
  A Brief Summary of Sorting Algorithm, Part 1
</a>

      </h3>
      

      <div class="article-info">
        <a href="/2019/10/13/sort-summary-1/"><span class="article-date">
  2019-10-13
</span>
</a>
        
	<span class="article-category tagcloud">
	<ul class="article-category-list"><li class="article-category-list-item"><a class="article-category-list-link" href="/categories/data-structure/">data structure</a></li></ul>
	</span>


        
	<span class="article-tag tagcloud">
		<ul class="article-tag-list"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/algorithm/">algorithm</a></li><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/python/">python</a></li><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/sorting/">sorting</a></li></ul>
	</span>


      </div>
      <div class="article-entry">
        
          <ol>
<li>Basics:<ul>
<li>in-place sorting vs. out-place sorting</li>
<li>internal sorting vs. external sorting</li>
<li>stable vs. unstable sorting</li>
</ul>
</li>
<li>Bubble Sort</li>
<li>Selection Sort</li>
<li>Insertion Sort</li>
<li>Merge Sort</li>
<li>Quick Sort</li>
<li>Heap Sort</li>
</ol>
<h3 id="internal-vs-external-sorting"><a href="#internal-vs-external-sorting" class="headerlink" title="internal vs. external sorting"></a>internal vs. external sorting</h3><p>Internal sorting and external sorting describes where the sorting occurs:</p>
<ul>
<li>internal sorting located entirely in memory</li>
<li>external sorting utilizes hard disk and external storage</li>
</ul>
<h3 id="stable-vs-unstable-sorting"><a href="#stable-vs-unstable-sorting" class="headerlink" title="stable vs. unstable sorting"></a>stable vs. unstable sorting</h3><p>A sorting algorithm is said to be stable if two objects with equal keys appear in the same order in sorted output as they appear in the input array to be sorted.</p>
<ul>
<li>stable sorting algorithms includes:<ol>
<li>Bubble Sort</li>
<li>Insertion Sort</li>
<li>Merge Sort</li>
<li>Count Sort</li>
</ol>
</li>
</ul>
<h3 id="Bubble-Sort"><a href="#Bubble-Sort" class="headerlink" title="Bubble Sort:"></a>Bubble Sort:</h3><p>Bubble Sort is a type of stable sorting algorithm. The algorithm compares two elements that are next to each other and swap two element is the left one is larger than the right one. Time complexity of bubble sort is O(n*n).<br><figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">bubbleSort</span><span class="params">(arr)</span>:</span> </span><br><span class="line">    n = len(arr) </span><br><span class="line">    <span class="keyword">for</span> i <span class="keyword">in</span> range(n): </span><br><span class="line">        <span class="keyword">for</span> j <span class="keyword">in</span> range(<span class="number">0</span>, n-i<span class="number">-1</span>): </span><br><span class="line">            <span class="keyword">if</span> arr[j] &gt; arr[j+<span class="number">1</span>] : </span><br><span class="line">                arr[j], arr[j+<span class="number">1</span>] = arr[j+<span class="number">1</span>], arr[j] </span><br><span class="line">    <span class="keyword">return</span> arr</span><br></pre></td></tr></table></figure></p>
<h3 id="Selection-Sort"><a href="#Selection-Sort" class="headerlink" title="Selection Sort:"></a>Selection Sort:</h3><p>In every iteration of selection sort, the minimum element (considering ascending order) from the unsorted subarray is picked and moved to the sorted sub-array. Selection sort can be done stably. Time complexity of selection sort is O(n*n).<br><figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">selectionSort</span><span class="params">(arr)</span>:</span></span><br><span class="line">    <span class="keyword">for</span> i <span class="keyword">in</span> range(len(arr)): </span><br><span class="line">        min_idx = i </span><br><span class="line">        <span class="keyword">for</span> j <span class="keyword">in</span> range(i+<span class="number">1</span>, len(arr)): </span><br><span class="line">            <span class="keyword">if</span> arr[min_idx] &gt; arr[j]: </span><br><span class="line">                min_idx = j </span><br><span class="line">        tmp = arr[i]</span><br><span class="line">        arr[i] = arr[min_idx]</span><br><span class="line">        arr[min_idx] = tmp</span><br><span class="line">    <span class="keyword">return</span> arr</span><br></pre></td></tr></table></figure></p>
<h3 id="Insertion-Sort"><a href="#Insertion-Sort" class="headerlink" title="Insertion Sort:"></a>Insertion Sort:</h3><p>Insertion sort is stable. In every iteration of insertion sort, the first element is selected and inserted into the correct location in the sorted half of the array. Time complexity of Insertion sort is O(n*n).<br><figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">insertionSort</span><span class="params">(arr)</span>:</span> </span><br><span class="line">    <span class="keyword">for</span> i <span class="keyword">in</span> range(<span class="number">1</span>, len(arr)): </span><br><span class="line">        key = arr[i] </span><br><span class="line">        j = i<span class="number">-1</span></span><br><span class="line">        <span class="keyword">while</span> j &gt;= <span class="number">0</span> <span class="keyword">and</span> key &lt; arr[j] : </span><br><span class="line">                arr[j + <span class="number">1</span>] = arr[j] </span><br><span class="line">                j -= <span class="number">1</span></span><br><span class="line">        arr[j + <span class="number">1</span>] = key </span><br><span class="line">    <span class="keyword">return</span> arr</span><br></pre></td></tr></table></figure></p>
<h3 id="Merge-Sort"><a href="#Merge-Sort" class="headerlink" title="Merge Sort:"></a>Merge Sort:</h3><p>Merge sort is stable. Merge Sort is a Divide and Conquer algorithm. It divides input array in two halves, calls itself for the two halves and then merges the two sorted halves. Time complexity is O(n*log(n)).<br><figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">mergeSort</span><span class="params">(arr)</span>:</span> </span><br><span class="line">    <span class="keyword">if</span> len(arr) &gt;<span class="number">1</span>: </span><br><span class="line">        mid = len(arr)//<span class="number">2</span></span><br><span class="line">        L = mergeSort(arr[:mid])</span><br><span class="line">        R = mergeSort(arr[mid:])</span><br><span class="line">        i = j = k = <span class="number">0</span></span><br><span class="line">        <span class="keyword">while</span> i &lt; len(L) <span class="keyword">and</span> j &lt; len(R): </span><br><span class="line">            <span class="keyword">if</span> L[i] &lt; R[j]: </span><br><span class="line">                arr[k] = L[i] </span><br><span class="line">                i+=<span class="number">1</span></span><br><span class="line">            <span class="keyword">else</span>: </span><br><span class="line">                arr[k] = R[j] </span><br><span class="line">                j+=<span class="number">1</span></span><br><span class="line">            k+=<span class="number">1</span></span><br><span class="line">        <span class="keyword">while</span> i &lt; len(L): </span><br><span class="line">            arr[k] = L[i] </span><br><span class="line">            i+=<span class="number">1</span></span><br><span class="line">            k+=<span class="number">1</span></span><br><span class="line">        <span class="keyword">while</span> j &lt; len(R): </span><br><span class="line">            arr[k] = R[j] </span><br><span class="line">            j+=<span class="number">1</span></span><br><span class="line">            k+=<span class="number">1</span></span><br><span class="line">    <span class="keyword">return</span> arr</span><br></pre></td></tr></table></figure></p>
<h3 id="Quick-Sort"><a href="#Quick-Sort" class="headerlink" title="Quick Sort:"></a>Quick Sort:</h3><p>For quick sort, we pick a random element as pivot. Compare each element with the pivot to create first half of the list smaller than the pivot and the second half larger than the pivot. After that, quick sort divide conquer two halves. Time complexity for quick sort is O(n*log(n)), worst case is O(n*n). Quick sort can be made stable.</p>
<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">partition</span><span class="params">(arr,low,high)</span>:</span> </span><br><span class="line">    i = (low<span class="number">-1</span>)</span><br><span class="line">    pivot = arr[high]</span><br><span class="line">    <span class="keyword">for</span> j <span class="keyword">in</span> range(low , high): </span><br><span class="line">        <span class="keyword">if</span>   arr[j] &lt; pivot: </span><br><span class="line">            i = i+<span class="number">1</span> </span><br><span class="line">            arr[i],arr[j] = arr[j],arr[i] </span><br><span class="line">    arr[i+<span class="number">1</span>],arr[high] = arr[high],arr[i+<span class="number">1</span>] </span><br><span class="line">    <span class="keyword">return</span> ( i+<span class="number">1</span> ) </span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">quickSort</span><span class="params">(arr,low,high)</span>:</span> </span><br><span class="line">    <span class="keyword">if</span> low &lt; high: </span><br><span class="line">        pi = partition(arr,low,high) </span><br><span class="line">        quickSort(arr, low, pi<span class="number">-1</span>) </span><br><span class="line">        quickSort(arr, pi+<span class="number">1</span>, high)</span><br></pre></td></tr></table></figure>
<h3 id="Heap-Sort"><a href="#Heap-Sort" class="headerlink" title="Heap Sort:"></a>Heap Sort:</h3><ol>
<li>Build a max heap from the input data.</li>
<li>At this point, the largest item is stored at the root of the heap. Replace it with the last item of the heap followed by reducing the size of heap by 1. Finally, heapify the root of tree.</li>
<li>Repeat above steps while size of heap is greater than 1.</li>
</ol>
<p>Heapify: this procedure calls itself recursively to move the max value to the top of the heap. Time complexity for heapify is O(log(n)) and time complexity for building a heap is O(n). Thus, heap sort gives the overall time complexity as O(n*log(n)).</p>
<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">heapify</span><span class="params">(arr, n, i)</span>:</span> </span><br><span class="line">    largest = i <span class="comment"># Initialize largest as root </span></span><br><span class="line">    l = <span class="number">2</span> * i + <span class="number">1</span>     <span class="comment"># left = 2*i + 1 </span></span><br><span class="line">    r = <span class="number">2</span> * i + <span class="number">2</span>     <span class="comment"># right = 2*i + 2 </span></span><br><span class="line">    <span class="comment"># left child  </span></span><br><span class="line">    <span class="keyword">if</span> l &lt; n <span class="keyword">and</span> arr[i] &lt; arr[l]: </span><br><span class="line">        largest = l </span><br><span class="line">    <span class="comment"># right child</span></span><br><span class="line">    <span class="keyword">if</span> r &lt; n <span class="keyword">and</span> arr[largest] &lt; arr[r]: </span><br><span class="line">        largest = r </span><br><span class="line">    <span class="comment"># change the root </span></span><br><span class="line">    <span class="keyword">if</span> largest != i: </span><br><span class="line">        arr[i],arr[largest] = arr[largest],arr[i] <span class="comment"># swap </span></span><br><span class="line">        <span class="comment"># Heapify upward </span></span><br><span class="line">        heapify(arr, n, largest) </span><br><span class="line">  </span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">heapSort</span><span class="params">(arr)</span>:</span> </span><br><span class="line">    n = len(arr) </span><br><span class="line">    <span class="keyword">for</span> i <span class="keyword">in</span> range(n, <span class="number">-1</span>, <span class="number">-1</span>): </span><br><span class="line">        heapify(arr, n, i) </span><br><span class="line">    <span class="keyword">for</span> i <span class="keyword">in</span> range(n<span class="number">-1</span>, <span class="number">0</span>, <span class="number">-1</span>): </span><br><span class="line">        arr[i], arr[<span class="number">0</span>] = arr[<span class="number">0</span>], arr[i] <span class="comment"># swap </span></span><br><span class="line">        heapify(arr, i, <span class="number">0</span>) </span><br><span class="line">    <span class="keyword">return</span> a</span><br></pre></td></tr></table></figure>
        
      </div>
    </div>

  

  
  
    
  

    <div class="post-list-item article">
      <h3 class="article-header">
        <a href="/2019/02/09/java-multi-thread/">
  Multiple Thread (Runnable vs. Thread), Part 1
</a>

      </h3>
      

      <div class="article-info">
        <a href="/2019/02/09/java-multi-thread/"><span class="article-date">
  2019-02-09
</span>
</a>
        
	<span class="article-category tagcloud">
	<ul class="article-category-list"><li class="article-category-list-item"><a class="article-category-list-link" href="/categories/backend/">backend</a></li></ul>
	</span>


        
	<span class="article-tag tagcloud">
		<ul class="article-tag-list"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/concurrency/">concurrency</a></li><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/java/">java</a></li></ul>
	</span>


      </div>
      <div class="article-entry">
        
          <ol>
<li>Multi-threading states</li>
<li>Java thread init methods</li>
</ol>
<h2 id="Multi-threading-states"><a href="#Multi-threading-states" class="headerlink" title="Multi-threading states:"></a>Multi-threading states:</h2><ol>
<li>new: &#x65B0;&#x5EFA;&#x72B6;&#x6001;&#xFF0C;&#x4FDD;&#x6301;&#x8FD9;&#x4E2A;&#x72B6;&#x6001;&#x76F4;&#x5230;&#x7A0B;&#x5E8F;start()</li>
<li>ready: &#x8C03;&#x7528;&#x4E86;start()&#xFF0C;&#x5C31;&#x7EEA;&#x72B6;&#x6001;&#x7684;&#x7EBF;&#x7A0B;&#x5904;&#x4E8E;&#x5C31;&#x7EEA;&#x961F;&#x5217;&#x4E2D;&#xFF0C;&#x8981;&#x7B49;&#x5F85;JVM&#x91CC;&#x7EBF;&#x7A0B;&#x8C03;&#x5EA6;&#x5668;&#x7684;&#x8C03;&#x5EA6;</li>
<li>running: &#x83B7;&#x53D6;&#x4E86;CPU&#x8D44;&#x6E90;&#xFF0C;&#x6267;&#x884C;run()&#x91CC;&#x9762;&#x7684;&#x6307;&#x4EE4;</li>
<li>suspend: &#x5931;&#x53BB;&#x6240;&#x5360;&#x7528;&#x8D44;&#x6E90;&#x4E4B;&#x540E;&#xFF0C;&#x8BE5;&#x7EBF;&#x7A0B;&#x5C31;&#x4ECE;&#x8FD0;&#x884C;&#x72B6;&#x6001;&#x8FDB;&#x5165;&#x963B;&#x585E;&#x72B6;&#x6001;&#x3002;&#x5728;&#x7761;&#x7720;&#x65F6;&#x95F4;&#x5DF2;&#x5230;&#x6216;&#x83B7;&#x5F97;&#x8BBE;&#x5907;&#x8D44;&#x6E90;&#x540E;&#x53EF;&#x4EE5;&#x91CD;&#x65B0;&#x8FDB;&#x5165;&#x5C31;&#x7EEA;&#x72B6;&#x6001;&#x3002;&#x53EF;&#x4EE5;&#x5206;&#x4E3A;&#x4E09;&#x79CD;<ul>
<li>&#x7B49;&#x5F85;&#x963B;&#x585E;: wait()</li>
<li>&#x540C;&#x6B65;&#x963B;&#x585E;: &#x7EBF;&#x7A0B;&#x5728;&#x83B7;&#x53D6;synchronized&#x540C;&#x6B65;&#x9501;&#x5931;&#x8D25;&#x540E;</li>
<li>&#x5176;&#x4ED6;&#x963B;&#x585E;: &#x5176;&#x4ED6;&#x963B;&#x585E;&#xFF1A;&#x901A;&#x8FC7;&#x8C03;&#x7528;&#x7EBF;&#x7A0B;&#x7684;sleep()&#x6216;join()&#x53D1;&#x51FA;&#x4E86;I/O&#x8BF7;&#x6C42;&#x65F6;&#xFF0C;&#x7EBF;&#x7A0B;&#x5C31;&#x4F1A;&#x8FDB;&#x5165;&#x5230;&#x963B;&#x585E;&#x72B6;&#x6001;</li>
</ul>
</li>
<li>dead: &#x4E00;&#x4E2A;&#x8FD0;&#x884C;&#x72B6;&#x6001;&#x7684;&#x7EBF;&#x7A0B;&#x5B8C;&#x6210;&#x4EFB;&#x52A1;&#x6216;&#x8005;&#x5176;&#x4ED6;&#x7EC8;&#x6B62;&#x6761;&#x4EF6;&#x53D1;&#x751F;&#x65F6;&#xFF0C;&#x8BE5;&#x7EBF;&#x7A0B;&#x5C31;&#x5207;&#x6362;&#x5230;&#x7EC8;&#x6B62;&#x72B6;&#x6001;</li>
</ol>
<h2 id="Java-thread-init-methods"><a href="#Java-thread-init-methods" class="headerlink" title="Java thread init methods:"></a>Java thread init methods:</h2><p>Java &#x63D0;&#x4F9B;&#x4E86;&#x4E09;&#x79CD;&#x521B;&#x5EFA;&#x7EBF;&#x7A0B;&#x7684;&#x65B9;&#x6CD5;&#xFF1A;</p>
<ul>
<li>&#x901A;&#x8FC7;&#x5B9E;&#x73B0;Runnable&#x63A5;&#x53E3;</li>
<li>&#x901A;&#x8FC7;&#x7EE7;&#x627F;Thread&#x7C7B;&#x672C;&#x8EAB;</li>
<li>&#x901A;&#x8FC7;Callable&#x548C;Future&#x521B;&#x5EFA;&#x7EBF;&#x7A0B;</li>
</ul>
<h2 id="Thread-example"><a href="#Thread-example" class="headerlink" title="Thread example:"></a>Thread example:</h2><p>The following code is an example with java, extending thread. A class can now be run as a individual class<br><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">// class extending Thread</span></span><br><span class="line"><span class="keyword">import</span> java.util.*;</span><br><span class="line"><span class="comment">// new class</span></span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">MyThread</span> <span class="keyword">extends</span> <span class="title">Thread</span> </span>{</span><br><span class="line">    <span class="keyword">private</span> <span class="keyword">int</span> ticket = <span class="number">10</span>;</span><br><span class="line">    <span class="keyword">private</span> String name;</span><br><span class="line">    <span class="keyword">private</span> Random rand = <span class="keyword">new</span> Random();</span><br><span class="line">    <span class="comment">// constructors</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="title">MyThread</span><span class="params">(String name)</span> </span>{</span><br><span class="line">        <span class="keyword">this</span>.name = name;</span><br><span class="line">        System.out.println(<span class="keyword">this</span>.name + <span class="string">&quot; starts with &quot;</span> + <span class="keyword">this</span>.ticket + <span class="string">&quot;.&quot;</span>);</span><br><span class="line">    }</span><br><span class="line">    <span class="comment">// Override the run function to implement functionality</span></span><br><span class="line">    <span class="meta">@Override</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">run</span><span class="params">()</span> </span>{</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; <span class="number">500</span>; i++) {</span><br><span class="line">            <span class="keyword">if</span> (<span class="keyword">this</span>.ticket &gt; <span class="number">0</span>) {</span><br><span class="line">                <span class="comment">// create a random number between two sales</span></span><br><span class="line">                <span class="keyword">int</span> nxt = rand.nextInt(<span class="number">20</span>) * <span class="number">10</span>;</span><br><span class="line">                <span class="keyword">this</span>.ticket--;</span><br><span class="line">                System.out.println(<span class="keyword">this</span>.name + <span class="string">&quot; sold a ticket, now has &quot;</span> + <span class="keyword">this</span>.ticket + <span class="string">&quot; tickets.&quot;</span>);</span><br><span class="line">                <span class="keyword">try</span> {</span><br><span class="line">                    Thread.sleep(nxt);</span><br><span class="line">                } <span class="keyword">catch</span> (InterruptedException e) {</span><br><span class="line">                    e.printStackTrace();</span><br><span class="line">                }</span><br><span class="line">            }</span><br><span class="line">        }</span><br><span class="line">        System.out.println(<span class="string">&quot;Now, &quot;</span> + <span class="keyword">this</span>.name + <span class="string">&quot; has ended.&quot;</span>);</span><br><span class="line">    }</span><br><span class="line">}</span><br><span class="line"><span class="comment">// method to run the class above</span></span><br><span class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">ThreadDemo</span> </span>{</span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">main</span><span class="params">(String[] args)</span> </span>{</span><br><span class="line">        System.out.println(<span class="string">&quot;start&quot;</span>);</span><br><span class="line">        MyThread mt1 = <span class="keyword">new</span> MyThread(<span class="string">&quot;Counter 1&quot;</span>);</span><br><span class="line">        MyThread mt2 = <span class="keyword">new</span> MyThread(<span class="string">&quot;Counter 2&quot;</span>);</span><br><span class="line">        MyThread mt3 = <span class="keyword">new</span> MyThread(<span class="string">&quot;Counter 3&quot;</span>);</span><br><span class="line">        mt1.start();</span><br><span class="line">        mt2.start();</span><br><span class="line">        mt3.start();</span><br><span class="line">    }</span><br><span class="line">}</span><br></pre></td></tr></table></figure></p>
<h2 id="Runnable-Example"><a href="#Runnable-Example" class="headerlink" title="Runnable Example:"></a>Runnable Example:</h2><p>The following code is an example with Runnable. The mutual information within a class is shared with all threads running that class. Runnable method will encounter race conditions without using locks.<br><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">import</span> java.util.concurrent.locks.Lock;</span><br><span class="line"><span class="keyword">import</span> java.util.concurrent.locks.ReentrantLock;</span><br><span class="line"><span class="keyword">import</span> java.util.Random;</span><br><span class="line"><span class="comment">// now using Runnable interface instead of extending a class</span></span><br><span class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">MyRunnable</span> <span class="keyword">implements</span> <span class="title">Runnable</span></span>{</span><br><span class="line">    <span class="keyword">private</span> <span class="keyword">int</span> ticket = <span class="number">30</span>;</span><br><span class="line">    <span class="keyword">private</span> Random rand = <span class="keyword">new</span> Random();</span><br><span class="line">    <span class="keyword">private</span> Lock lock = <span class="keyword">new</span> ReentrantLock();</span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="title">MyRunnable</span><span class="params">()</span> </span>{</span><br><span class="line">        System.out.println(<span class="string">&quot;This class starts with &quot;</span> + <span class="keyword">this</span>.ticket + <span class="string">&quot; tickets.&quot;</span>);</span><br><span class="line">    }</span><br><span class="line">    <span class="comment">// overriding the run method just as before</span></span><br><span class="line">    <span class="meta">@Override</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">run</span><span class="params">()</span> </span>{</span><br><span class="line">        <span class="keyword">while</span> (<span class="keyword">this</span>.ticket &gt; <span class="number">0</span>) {</span><br><span class="line">            <span class="comment">// tryLock() checks if the lock is available, takes the lock and return true if yes, else return false</span></span><br><span class="line">            <span class="keyword">if</span> (lock.tryLock()){</span><br><span class="line">                <span class="keyword">try</span> {</span><br><span class="line">                    <span class="comment">// command to execute with the lock</span></span><br><span class="line">                    System.out.println(Thread.currentThread().getName() + <span class="string">&quot; acquired lock.&quot;</span>);</span><br><span class="line">                    <span class="keyword">this</span>.ticket--;</span><br><span class="line">                    System.out.println(Thread.currentThread().getName() + <span class="string">&quot; sold a ticket, now has &quot;</span> + <span class="keyword">this</span>.ticket + <span class="string">&quot; tickets.&quot;</span>);</span><br><span class="line">                } <span class="keyword">catch</span> (Exception e) {</span><br><span class="line">                    System.err.println(e);</span><br><span class="line">                } <span class="keyword">finally</span> {</span><br><span class="line">                    <span class="comment">// releasing the lock</span></span><br><span class="line">                    System.out.println(Thread.currentThread().getName() + <span class="string">&quot; released lock.&quot;</span>);</span><br><span class="line">                    lock.unlock();</span><br><span class="line">                }</span><br><span class="line">                <span class="comment">// wait for a random length after selling a ticket</span></span><br><span class="line">                <span class="keyword">int</span> nxt = rand.nextInt(<span class="number">20</span>) * <span class="number">10</span>;</span><br><span class="line">                <span class="keyword">try</span> {</span><br><span class="line">                    Thread.sleep(nxt);</span><br><span class="line">                } <span class="keyword">catch</span> (InterruptedException e) {</span><br><span class="line">                    e.printStackTrace();</span><br><span class="line">                }</span><br><span class="line">            } </span><br><span class="line">            <span class="comment">// if lock is not available, wait</span></span><br><span class="line">            <span class="keyword">else</span> {</span><br><span class="line">                <span class="keyword">try</span> {</span><br><span class="line">                    Thread.sleep(<span class="number">10</span>);</span><br><span class="line">                } <span class="keyword">catch</span> (InterruptedException e) {</span><br><span class="line">                    e.printStackTrace();</span><br><span class="line">                }</span><br><span class="line">            }</span><br><span class="line">        }</span><br><span class="line">        System.out.println(<span class="string">&quot;Now, &quot;</span> + Thread.currentThread().getName() + <span class="string">&quot; has ended.&quot;</span>);</span><br><span class="line">    }</span><br><span class="line">}</span><br></pre></td></tr></table></figure></p>

        
      </div>
    </div>

  

  
  
    
  

    <div class="post-list-item article">
      <h3 class="article-header">
        <a href="/2019/01/20/Django-basic-1/">
  Django Basics, Part 1
</a>

      </h3>
      

      <div class="article-info">
        <a href="/2019/01/20/Django-basic-1/"><span class="article-date">
  2019-01-20
</span>
</a>
        
	<span class="article-category tagcloud">
	<ul class="article-category-list"><li class="article-category-list-item"><a class="article-category-list-link" href="/categories/backend/">backend</a></li></ul>
	</span>


        
	<span class="article-tag tagcloud">
		<ul class="article-tag-list"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/backend/">backend</a></li><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/django/">django</a></li><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/python/">python</a></li></ul>
	</span>


      </div>
      <div class="article-entry">
        
          <h2 id="Django-Directory-Levels"><a href="#Django-Directory-Levels" class="headerlink" title="Django Directory Levels"></a>Django Directory Levels</h2><ol>
<li>manage.py: we use this to communicate with Django server</li>
<li>project directory:<ol>
<li>__init__.py: tells Django to use directory as a python package</li>
<li>settings.py: Django configuration file</li>
<li>urls.py: url schemaa</li>
<li>wsgi.py: project and wsgi integration web server</li>
</ol>
</li>
</ol>
<h2 id="Database-MySQL-config"><a href="#Database-MySQL-config" class="headerlink" title="Database (MySQL) config"></a>Database (MySQL) config</h2><ul>
<li>dependencies used:<br>  mysql                     5.7.24               h56848d4_0<br>  mysql-connector-c         6.1.11               hccea1a4_0<br>  mysql-connector-python    8.0.17           py27h3febbb0_0    anaconda<br>  mysql-python              1.2.5            py27h1de35cc_0    anaconda<br>  pymysql                   0.9.3                    py27_0  </li>
<li><p>__init__.py, add the following code: </p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">import pymysql</span><br><span class="line">pymysql.install_as_MySQLdb()</span><br></pre></td></tr></table></figure>
</li>
<li><p>in settings.py: add database configurations to connect to the database</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br></pre></td><td class="code"><pre><span class="line">DATABASES = {</span><br><span class="line">    &apos;default&apos;: {</span><br><span class="line">        &apos;ENGINE&apos;: &apos;django.db.backends.mysql&apos;,</span><br><span class="line">        &apos;NAME&apos;: # server name</span><br><span class="line">        &apos;USER&apos;: # user name</span><br><span class="line">        &apos;PASSWORD&apos;: # password</span><br><span class="line">        &apos;HOST&apos;: &apos;localhost&apos;,</span><br><span class="line">        &apos;PORT&apos;: &apos;3306&apos;,</span><br><span class="line">    }</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
</li>
</ul>
<h2 id="new-application"><a href="#new-application" class="headerlink" title="new application"></a>new application</h2><ul>
<li><p>init new application:  </p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">python manage.py startapp &lt;myApp&gt;</span><br></pre></td></tr></table></figure>
</li>
<li><p>codes above creates:</p>
<ul>
<li>admin.py: website config</li>
<li>models.py: model</li>
<li>views.py: view</li>
</ul>
</li>
<li>In setting, add <myapp> to INSTALLED_APP:<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line">INSTALLED_APPS = [</span><br><span class="line">    &apos;django.contrib.admin&apos;,</span><br><span class="line">    &apos;django.contrib.auth&apos;,</span><br><span class="line">    &apos;django.contrib.contenttypes&apos;,</span><br><span class="line">    &apos;django.contrib.sessions&apos;,</span><br><span class="line">    &apos;django.contrib.messages&apos;,</span><br><span class="line">    &apos;django.contrib.staticfiles&apos;,</span><br><span class="line">    &apos;myApp&apos;</span><br><span class="line">]</span><br></pre></td></tr></table></figure>
</myapp></li>
</ul>
<h2 id="models-py-file"><a href="#models-py-file" class="headerlink" title="models.py file"></a>models.py file</h2><ul>
<li><p>example models.py can be as the following:</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br></pre></td><td class="code"><pre><span class="line"># -*- coding: utf-8 -*-</span><br><span class="line">from __future__ import unicode_literals</span><br><span class="line">from django.db import models</span><br><span class="line"></span><br><span class="line"># Create your models here.</span><br><span class="line">class Grades(models.Model):</span><br><span class="line">    gname = models.CharField(max_length=20)</span><br><span class="line">    gdate = models.DateTimeField()</span><br><span class="line">    ggirlnum = models.IntegerField()</span><br><span class="line">    gboynum = models.IntegerField()</span><br><span class="line">    isDelete = models.BooleanField(default=False)</span><br><span class="line">    </span><br><span class="line">    def __str__(self):</span><br><span class="line">        return &quot;%s-%d-%d&quot;%(self.gname, self.gboynum, self.ggrilnum)</span><br><span class="line"></span><br><span class="line"></span><br><span class="line">class Students(models.Model):</span><br><span class="line">    sname = models.CharField(max_length=20)</span><br><span class="line">    sgender = models.BooleanField(default=True)</span><br><span class="line">    sage = models.IntegerField()</span><br><span class="line">    scontend = models.CharField(max_length=20)</span><br><span class="line">    isDelete = models.BooleanField(default=False)</span><br><span class="line">    sgrade = models.ForeignKey(&quot;Grades&quot;)</span><br><span class="line">    </span><br><span class="line">    def __str__(self):</span><br><span class="line">            return &quot;%s-%d-%s&quot;%(self.sname, self.sage, self.scontend)</span><br></pre></td></tr></table></figure>
</li>
<li><p>make migration and execute migration file: will create database according to models.py</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">python manage.py makemigrations # create migration file</span><br><span class="line">python manage.py migrate        # execute migration file</span><br></pre></td></tr></table></figure>
</li>
</ul>
<h2 id="To-add-new-entries-with-manage-py-shell"><a href="#To-add-new-entries-with-manage-py-shell" class="headerlink" title="To add new entries with manage.py shell"></a>To add new entries with manage.py shell</h2><ul>
<li><p>enter shell:</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">python manage.py shell</span><br></pre></td></tr></table></figure>
</li>
<li><p>import packages in shell:</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line">from myApp.models import Grades, Students</span><br><span class="line">from django.utils import timezone</span><br><span class="line">from datetime import *</span><br></pre></td></tr></table></figure>
</li>
<li><p>add new entry to db:</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></td><td class="code"><pre><span class="line">grade1 = Grades()</span><br><span class="line">grade1.gname = &quot;something&quot;</span><br><span class="line">grade1.gdate = datetime(year=,month=,day=)</span><br><span class="line">grade1.ggirlnum = 70</span><br><span class="line">grade1.gboynum = 35</span><br><span class="line">grade1.save()</span><br></pre></td></tr></table></figure>
</li>
<li><p>some other command:</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></td><td class="code"><pre><span class="line">Grades.objects.all()    # get all data entries in Grades</span><br><span class="line">g = Grades.objects.get(pk=1)    # get the 1st object in Grades</span><br><span class="line">g.gboynum = 45</span><br><span class="line">g.save()    # alternate existing data</span><br><span class="line">d.delete()  # delete, including the one in db</span><br><span class="line">stu1 = g.students_set.create(sname=...)     # add new student with one line</span><br></pre></td></tr></table></figure>
</li>
</ul>
<h2 id="run-server"><a href="#run-server" class="headerlink" title="run server:"></a>run server:</h2><ul>
<li><p>execute:</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">python manage.py runserver ip:port</span><br></pre></td></tr></table></figure>
</li>
<li><p>Admin:</p>
<ul>
<li>publish content</li>
<li>add/modify/delete content</li>
<li>add &#x201C;&#x2018;django.contrib.admin&#x2019;&#x201D; in INSTALLED_APPS</li>
<li>exists by defualt</li>
<li>add &#x201C;/admin&#x201D; and log in</li>
<li>change language or timezone based on preference</li>
</ul>
</li>
</ul>
<p>(to be continued&#x2026;)</p>

        
      </div>
    </div>

  






          <div class="main-footer">
  
    © 2019 Zexi &#34;Josh&#34; Jin - Powered by <a href="http://hexo.io" target="_blank">Hexo</a> - Theme <a href="https://github.com/denjones/hexo-theme-chan" target="_blank">Chan</a>
  
</div>

      
        </div>
      
    </section></div>
  </div>
  <script src="//apps.bdimg.com/libs/jquery/2.1.4/jquery.min.js"></script>

  <link rel="stylesheet" href="/PhotoSwipe/photoswipe.css">
  <link rel="stylesheet" href="/PhotoSwipe/default-skin/default-skin.css">

  <!-- Root element of PhotoSwipe. Must have class pswp. -->
  <div class="pswp" tabindex="-1" role="dialog" aria-hidden="true">

    <!-- Background of PhotoSwipe.
             It's a separate element as animating opacity is faster than rgba(). -->
    <div class="pswp__bg"></div>

    <!-- Slides wrapper with overflow:hidden. -->
    <div class="pswp__scroll-wrap">

      <!-- Container that holds slides.
                PhotoSwipe keeps only 3 of them in the DOM to save memory.
                Don't modify these 3 pswp__item elements, data is added later on. -->
      <div class="pswp__container">
        <div class="pswp__item"></div>
        <div class="pswp__item"></div>
        <div class="pswp__item"></div>
      </div>

      <!-- Default (PhotoSwipeUI_Default) interface on top of sliding area. Can be changed. -->
      <div class="pswp__ui pswp__ui--hidden">

        <div class="pswp__top-bar">

          <!--  Controls are self-explanatory. Order can be changed. -->

          <div class="pswp__counter"></div>

          <button class="pswp__button pswp__button--close" title="Close (Esc)"></button>

          <button class="pswp__button pswp__button--share" title="Share"></button>

          <button class="pswp__button pswp__button--fs" title="Toggle fullscreen"></button>

          <button class="pswp__button pswp__button--zoom" title="Zoom in/out"></button>

          <!-- Preloader demo http://codepen.io/dimsemenov/pen/yyBWoR -->
          <!-- element will get class pswp__preloader--active when preloader is running -->
          <div class="pswp__preloader">
            <div class="pswp__preloader__icn">
              <div class="pswp__preloader__cut">
                <div class="pswp__preloader__donut"></div>
              </div>
            </div>
          </div>
        </div>

        <div class="pswp__share-modal pswp__share-modal--hidden pswp__single-tap">
          <div class="pswp__share-tooltip"></div>
        </div>

        <button class="pswp__button pswp__button--arrow--left" title="Previous (arrow left)"></button>

        <button class="pswp__button pswp__button--arrow--right" title="Next (arrow right)"></button>

        <div class="pswp__caption">
          <div class="pswp__caption__center"></div>
        </div>
      </div>
    </div>
  </div>

  <script src="/PhotoSwipe/photoswipe.js"></script>
  <script src="/PhotoSwipe/photoswipe-ui-default.js"></script>


<script src="/perfect-scrollbar/js/min/perfect-scrollbar.min.js"></script>
<script src="/scripts/main.js"></script>

</div><!-- hexo-inject:begin --><!-- hexo-inject:end --></body>
</html>
